home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 395_01 / avl / testsl.c < prev   
Encoding:
C/C++ Source or Header  |  1993-08-27  |  11.4 KB  |  552 lines
  1. /* test sortlist */
  2.  
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5.  
  6. #include "sortlist.h"
  7. #include "slintrnl.h"
  8.  
  9. typedef unsigned int UINT;
  10.  
  11. #define MAX_ELEM_WORDS 50
  12. UINT elem_words;
  13.  
  14. #define MAX_LIST 2000
  15. char in[MAX_LIST];
  16. UINT max_elems;
  17.  
  18. UINT min_num_elems[30];
  19.  
  20. int i1 = 0, i2 = 0, i3 = 0, i4 = 0, i5 = 0;
  21. UINT u1 = 0, u2 = 0, u3 = 0, u4 = 0, u5 = 0, u6 = 0, u7 = 0, u8 = 0, u9 = 0;
  22.  
  23. void chk(int cond, char *msg)
  24.   {
  25.     if (cond)
  26.       return;
  27.  
  28.     printf("ERROR: %s\n", msg);
  29.     printf("i1=%d i2=%d i3=%d i4=%d i5=%d\n", i1, i2, i3, i4, i5);
  30.     printf("u1=%u u2=%u u3=%u u4=%u u5=%u u6=%u\n", u1, u2, u3, u4, u5, u6);
  31.     printf("u7=%u u8=%u u9=%u\n", u7, u8, u9);
  32.  
  33.     exit(1);
  34.   }
  35.  
  36. void set_elem(UINT *elem, UINT val)
  37.   {
  38.     UINT i;
  39.  
  40.     for (i = 0; i < elem_words; i++)
  41.       elem[i] = val + i;
  42.  
  43.     return;
  44.   }
  45.  
  46. void check_elem(const UINT *elem)
  47.   {
  48.     for (u7 = 1; u7 < elem_words; u7++)
  49.       {
  50.     u8 = elem[0] + u7;
  51.     u9 = elem[u7];
  52.     chk(u8 == u9, "corrupt element");
  53.       }
  54.  
  55.     return;
  56.   }
  57.  
  58. typedef struct
  59.   {
  60.     int depth;
  61.     UINT num_elems;
  62.   }
  63. TREE_INFO;
  64.  
  65. void check_subtree(void *tree, TREE_INFO *info)
  66.   {
  67.     if (!tree)
  68.       {
  69.     info->depth = 0;
  70.     info->num_elems = 0;
  71.       }
  72.     else
  73.       {
  74.     TREE_INFO l, g;
  75.     int bal = NODE(tree)->balance;
  76.     UINT val = ((UINT *) ELEM_IN_NODE(tree))[0];
  77.  
  78.     check_subtree(NODE(tree)->branch[LESS_BRANCH], &l);
  79.     check_subtree(NODE(tree)->branch[GREATER_BRANCH], &g);
  80.  
  81.     if (bal != (g.depth - l.depth))
  82.       {
  83.         printf("bad balance: val=%d bal=%d l=%d g=%d\n",
  84.            val, bal, l.depth, g.depth);
  85.         exit(1);
  86.       }
  87.  
  88.     info->depth = (l.depth > g.depth ? l.depth : g.depth) + 1;
  89.     info->num_elems = l.num_elems + g.num_elems + 1;
  90.  
  91.     if (info->num_elems < min_num_elems[info->depth])
  92.       {
  93.         printf("bad size: val=%u depth=%d num elems=%u min elems=%u\n",
  94.            val, info->depth, info->num_elems,
  95.            min_num_elems[info->depth]);
  96.         exit(1);
  97.       }
  98.       }
  99.     return;
  100.   }
  101.  
  102. void check_tree(SORT_LIST *sl, char *msg)
  103.   {
  104.     TREE_INFO i;
  105.     check_subtree(sl->tree, &i);
  106.  
  107.     printf("%s: depth=%d num elems=%d\n", msg, i.depth, i.num_elems);
  108.  
  109.     return;
  110.   }
  111.  
  112. void add_elems(SORT_LIST *sl, UINT start_index, UINT count, UINT step)
  113.   {
  114.     UINT e[MAX_ELEM_WORDS];
  115.     SL_RESULT r;
  116.  
  117.     u1 = start_index;
  118.     u2 = step;
  119.  
  120.     while (count--)
  121.       {
  122.     set_elem(e, 2 * u1 + 1);
  123.  
  124.     if (!(in[u1]))
  125.       {
  126.         r = add_sort_list(sl, (void *) e);
  127.         chk(r != SL_MEM_ALLOC_FAIL, "mem. allocation failure");
  128.         chk(r == SL_SUCCESS, "said dup. key, but none");
  129.         in[u1] = 1;
  130.       }
  131.     chk(SL_SUCCESS != add_sort_list(sl, (void *) e),
  132.             "allowed dup. key");
  133.  
  134.     u1 += u2;
  135.     u1 %= max_elems;
  136.       }
  137.  
  138.     return;
  139.   }
  140.  
  141. void del_elems(SORT_LIST *sl, UINT start_index, UINT count, UINT step)
  142.   {
  143.     UINT e[MAX_ELEM_WORDS],val;
  144.  
  145.     u1 = start_index;
  146.     u2 = step;
  147.  
  148.     while (count--)
  149.       {
  150.     val = 2 * u1 + 1;
  151.     if (in[u1])
  152.       {
  153.         chk(SL_SUCCESS == delete_sort_list(sl, (void *) &val, (void *) e),
  154.                                        "del. said no match when is");
  155.         check_elem(e);
  156.         u3 = ((UINT *) e)[0];
  157.         chk(u3 == val, "del. wrong element");
  158.         in[u1] = 0;
  159.       }
  160.     chk(SL_NO_MATCH == delete_sort_list(sl, (void *) &val, (void *) e),
  161.                         "del. said match when none");
  162.  
  163.     u1 += u2;
  164.     u1 %= max_elems;
  165.       }
  166.  
  167.     return;
  168.   }
  169.  
  170. int next_elem(void *elem, void *idx)
  171.   {
  172.     #define INDEX (*((UINT *) idx))
  173.  
  174.     if (INDEX == 666)
  175.       return(1);
  176.  
  177.     set_elem(elem, 2 * INDEX + 1);
  178.     in[INDEX] = 1;
  179.     INDEX++;
  180.  
  181.     return(0);
  182.   }
  183.  
  184. int e_e_compare(const void *e1, const void *e2)
  185.   {
  186.     #define E1 ((const UINT *) e1)
  187.     #define E2 ((const UINT *) e2)
  188.  
  189.     check_elem(E1);
  190.     check_elem(E2);
  191.  
  192.     return(((int) *E1) - ((int) *E2));
  193.   }
  194.  
  195. int k_e_compare(const void *k, const void *e)
  196.   {
  197.     #define K ((const UINT *) k)
  198.     #define E ((const UINT *) e)
  199.  
  200.     check_elem(E);
  201.  
  202.     return(((int) *K) - ((int) *E));
  203.   }
  204.  
  205. void do_find(SORT_LIST *sl, UINT match_type, UINT try, UINT should_find)
  206.   {
  207.     UINT *f;
  208.  
  209.     u1 = match_type;
  210.     u2 = try;
  211.     u3 = should_find;
  212.  
  213.     f = (UINT *) find_sort_list(sl, u1, (void *) &u2);
  214.     if (u3)
  215.       {
  216.         chk(!!f, "nothing found");
  217.     check_elem(f);
  218.     u4 = ((UINT *) f)[0];
  219.     chk(u4 == u3, "wrong element found");
  220.       }
  221.     else
  222.       {
  223.     if (f)
  224.       u4 = ((UINT *) f)[0];
  225.         chk(!f, "find should have failed");
  226.       }
  227.     return;
  228.   }
  229.  
  230. /* test tree with at least 1 element */
  231. void test_find(SORT_LIST *sl)
  232.   {
  233.     UINT i, j, last = 0;
  234.  
  235.     for (i = 0; !in[i]; i++)
  236.       ;
  237.     do_find(sl, MATCH_LEAST, 0, 2 * i + 1);
  238.     for (i = max_elems - 1; !in[i]; i--)
  239.       ;
  240.     do_find(sl, MATCH_GREATEST, 0, 2 * i + 1);
  241.  
  242.  
  243.     for (i = 0; i < max_elems; i++)
  244.       {
  245.     if (in[i])
  246.       {
  247.         j = 2 * i;
  248.  
  249.         do_find(sl, MATCH_EQUAL, j, 0);
  250.         do_find(sl, MATCH_GREATER, j, j + 1);
  251.         do_find(sl, MATCH_GREATER_EQUAL, j, j + 1);
  252.  
  253.         j++;
  254.  
  255.         do_find(sl, MATCH_EQUAL, j, j);
  256.         do_find(sl, MATCH_GREATER_EQUAL, j, j);
  257.         do_find(sl, MATCH_LESS_EQUAL, j, j);
  258.         if (last)
  259.           {
  260.             do_find(sl, MATCH_GREATER, last, j);
  261.             do_find(sl, MATCH_LESS, j, last);
  262.           }
  263.         last = j;
  264.  
  265.         j++;
  266.  
  267.         do_find(sl, MATCH_EQUAL, j, 0);
  268.         do_find(sl, MATCH_LESS, j, j - 1);
  269.         do_find(sl, MATCH_LESS_EQUAL, j, j - 1);
  270.       }
  271.  
  272.       }
  273.  
  274.     return;
  275.   }
  276.  
  277. void test_find_empty(SORT_LIST *sl)
  278.   {
  279.     int val = max_elems + 1;
  280.     do_find(sl, MATCH_LEAST, 0, 0);
  281.     do_find(sl, MATCH_GREATEST, 0, 0);
  282.     do_find(sl, MATCH_EQUAL, val, 0);
  283.     do_find(sl, MATCH_GREATER, val, 0);
  284.     do_find(sl, MATCH_GREATER_EQUAL, val, 0);
  285.     do_find(sl, MATCH_LESS, val, 0);
  286.     do_find(sl, MATCH_LESS_EQUAL, val, 0);
  287.     return;
  288.   }
  289.  
  290. /* for apply test:
  291.    u1 - forward flag
  292.    u2 - start bound
  293.    u3 - end bound
  294.    u4 - index of next apply element
  295.    u5 - end seen flag
  296. */
  297.  
  298. void next_apply(void)
  299.   {
  300.     do
  301.       {
  302.     if (u1)
  303.       {
  304.         if (u4 == max_elems)
  305.           return;
  306.         u4++;
  307.       }
  308.     else
  309.       {
  310.         if (u4 == 0)
  311.           {
  312.         u4 = max_elems;
  313.         return;
  314.           }
  315.         u4--;
  316.       }
  317.       }
  318.     while (!in[u4]);
  319.  
  320.     return;
  321.   }
  322.  
  323. char param_string[] = "second apply param";
  324.  
  325. int apply_func(void *elem, void *param)
  326.   {
  327.     chk(!u5, "apply past end bound");
  328.     chk(u4 < max_elems, "apply should have stopped");
  329.  
  330.     chk(param == (void *) param_string, "bad param. apply");
  331.     check_elem(elem);
  332.     if (u1)
  333.       u5 = u3 < (2 * u4 + 1);
  334.     else
  335.       u5 = u2 > (2 * u4 + 1);
  336.     if (!u5)
  337.       {
  338.     u6 = ((UINT *) elem)[0];
  339.     chk (u6 == (2 * u4 + 1), "apply wrong order");
  340.     next_apply();
  341.       }
  342.  
  343.     return(u5);
  344.   }
  345.  
  346. /* at least 1 element */
  347. void test_apply(SORT_LIST *sl)
  348.   {
  349.     UINT bottom_index, top_index;
  350.  
  351.     for (bottom_index = 0; !in[bottom_index]; bottom_index++)
  352.       ;
  353.  
  354.     u1 = 1;
  355.     u3 = 2 * (max_elems + 1);
  356.     u4 = bottom_index;
  357.     u5 = 0;
  358.     chk(apply_sort_list(sl, apply_func, (void *) param_string, u1,
  359.                         (void *) 0) == 0, "bad apply no start");
  360.  
  361.     for (top_index = max_elems - 1; !in[top_index]; top_index--)
  362.       ;
  363.     for ( ; ; )
  364.       {
  365.     u2 = 2 * bottom_index;
  366.     u3 = 2 * (top_index + 1);
  367.     u1 = 1;
  368.     u4 = bottom_index;
  369.     u5 = 0;
  370.     chk(apply_sort_list(sl, apply_func, (void *) param_string, u1,
  371.                 (void *) &u2) == (u4 != max_elems),
  372.                             "bad apply w/start");
  373.     u1 = 0;
  374.     u4 = top_index;
  375.     u5 = 0;
  376.     chk(apply_sort_list(sl, apply_func, (void *) param_string, u1,
  377.                 (void *) &u3) == (u4 != max_elems),
  378.                             "bad apply w/start");
  379.     u2++;
  380.         u3--;
  381.     u1 = 1;
  382.     u4 = bottom_index;
  383.     u5 = 0;
  384.     chk(apply_sort_list(sl, apply_func, (void *) param_string, u1,
  385.                 (void *) &u2) == (u4 != max_elems),
  386.                             "bad apply w/start");
  387.     u1 = 0;
  388.     u4 = top_index;
  389.     u5 = 0;
  390.     chk(apply_sort_list(sl, apply_func, (void *) param_string, u1,
  391.                 (void *) &u3) == (u4 != max_elems),
  392.                             "bad apply w/start");
  393.  
  394.     if (bottom_index == top_index)
  395.       break;
  396.  
  397.     do
  398.       bottom_index++;
  399.     while (!(in[bottom_index]));
  400.     do
  401.       top_index--;
  402.     while (!(in[top_index]));
  403.  
  404.     if (bottom_index > top_index)
  405.       break;
  406.       }
  407.     return;
  408.   }
  409.  
  410. void test_apply_empty(SORT_LIST *sl)
  411.   {
  412.     u5 = 1;
  413.     chk(apply_sort_list(sl, apply_func, (void *) param_string, 1,
  414.             (void *) &u3) == 0, "bad apply empty");
  415.     chk(apply_sort_list(sl, apply_func, (void *) param_string, 0,
  416.             (void *) &u3) == 0, "bad apply empty");
  417.     return;
  418.   }
  419.  
  420. int main()
  421.   {
  422.     SORT_LIST sl;
  423.     UINT i;
  424.     SL_RESULT r;
  425.  
  426.     min_num_elems[0] = 0;
  427.     min_num_elems[1] = 1;
  428.     for (i = 2; i < 30; i++)
  429.       min_num_elems[i] = min_num_elems[i - 1] + min_num_elems[i - 2] + 1;
  430.  
  431.     max_elems = 100;
  432.     elem_words = 1;
  433.  
  434.     printf("max elems=%u elem words=%u\n", max_elems, elem_words);
  435.  
  436.     for (i = 0; i < max_elems; i++)
  437.       in[i] = 0;
  438.  
  439.     init_sort_list(&sl, elem_words * sizeof(UINT), e_e_compare, k_e_compare);
  440.     check_tree(&sl, "after init");
  441.     test_find_empty(&sl);
  442.     test_apply_empty(&sl);
  443.  
  444.     add_elems(&sl, 69, 1, 0);
  445.  
  446.     check_tree(&sl,"after add 1");
  447.     test_find(&sl);
  448.     test_apply(&sl);
  449.  
  450.     add_elems(&sl, 30, 90, 13);
  451.  
  452.     check_tree(&sl, "after add 2");
  453.     test_find(&sl);
  454.     test_apply(&sl);
  455.  
  456.     del_elems(&sl, 30, 90, 87);
  457.  
  458.     check_tree(&sl, "after del 1");
  459.     test_find(&sl);
  460.     test_apply(&sl);
  461.  
  462.     del_elems(&sl, 1, 100, 1);
  463.  
  464.     check_tree(&sl, "after del 2");
  465.     test_find_empty(&sl);
  466.     test_apply_empty(&sl);
  467.  
  468.     add_elems(&sl, 30, 100, 99);
  469.  
  470.     check_tree(&sl, "after add 3");
  471.     test_find(&sl);
  472.     test_apply(&sl);
  473.  
  474.     clear_sort_list(&sl);
  475.  
  476.     check_tree(&sl, "after clear");
  477.     test_find_empty(&sl);
  478.     test_apply_empty(&sl);
  479.  
  480.     max_elems = 2000;
  481.     elem_words = 50;
  482.  
  483.     printf("max elems=%u elem words=%u\n", max_elems, elem_words);
  484.  
  485.     for (i = 0; i < max_elems; i++)
  486.       in[i] = 0;
  487.  
  488.     init_sort_list(&sl, elem_words * sizeof(UINT), e_e_compare, k_e_compare);
  489.  
  490.     check_tree(&sl, "after init");
  491.     test_find_empty(&sl);
  492.     test_apply_empty(&sl);
  493.  
  494.     add_elems(&sl, 699, 1, 0);
  495.  
  496.     check_tree(&sl, "after add 1");
  497.     test_find(&sl);
  498.     test_apply(&sl);
  499.  
  500.     add_elems(&sl, 300, 1800, 13 * 13);
  501.  
  502.     check_tree(&sl, "after add 2");
  503.     test_find(&sl);
  504.  
  505.     del_elems(&sl, 300, 1850, (2000 - 13 * 13));
  506.  
  507.     check_tree(&sl, "after del 1");
  508.     test_find(&sl);
  509.     test_apply(&sl);
  510.  
  511.     del_elems(&sl, 1, 2000, 1);
  512.  
  513.     check_tree(&sl, "after del 2");
  514.     test_find_empty(&sl);
  515.     test_apply_empty(&sl);
  516.  
  517.     add_elems(&sl, 300, 2000, 999);
  518.  
  519.     check_tree(&sl, "after add 3");
  520.     test_find(&sl);
  521.  
  522.     clear_sort_list(&sl);
  523.  
  524.     check_tree(&sl, "after clear");
  525.     test_find_empty(&sl);
  526.     test_apply_empty(&sl);
  527.  
  528.     for (i = 0; i < max_elems; i++)
  529.       in[i] = 0;
  530.  
  531.     i = 0;
  532.     chk(build_sort_list(&sl, 500, next_elem, (void *) &i) == SL_SUCCESS,
  533.         "bad build");
  534.  
  535.     check_tree(&sl, "after build");
  536.     test_find(&sl);
  537.     chk(i == 500, "i should be 500");
  538.  
  539.     clear_sort_list(&sl);
  540.  
  541.     i = 500;
  542.     chk(build_sort_list(&sl, 200, next_elem, (void *) &i) == SL_ABORT,
  543.         "build should have aborted");
  544.     check_tree(&sl, "after bad build");
  545.     test_find_empty(&sl);
  546.     chk(i == 666, "i should be 666");
  547.  
  548.     printf("SUCCESS!\n");
  549.  
  550.     return(0);
  551.   }
  552.